Marker patterns can be added to objects or scenes to allow automatic systems to find correspondence between points in the world and points in camera images, and to find correspondences between points in one camera image and points in another camera image. The former has application in positioning, robotics, and augmented reality applications, the latter has application in automatic computer modeling to provide the coordinates of world points for applications of the former. Furthermore, marker patterns can be used to contain information relating to various products. For example, marker patterns printed out and mounted on a piece of equipment would allow an augmented reality system to aid a person constructing or servicing this equipment by overlaying virtual graphics with instructions over their view (known as “Augmented Reality”), with the aid of an image sensor (light capturing device such as camera, video camera, digital camera, etc) and the computer vision techniques that locate these patterns. Furthermore with camera cell phones and PDAs becoming commonly available, a marker could be used to link a user to an URL address providing access to a series of images, advertisement etc. Another example of use includes a robot which could navigate by detecting markers placed in its environment. Using computer vision, cameras and cameras cell phones to determine relative pose is an inexpensive and accurate approach useful to many domains.
Measurements such as position and orientation of objects, sensing of industrial and weather values, are possible with “smart cameras” which are system combinations of image sensing and processing, and with consumer mobile devices such as mobile phones, tablets, and wearable technology. Measurements such as position and orientation are useful for the above mentioned augmented reality applications. Many measurements require the identification of points in the environment, thus the creation of a list of correspondences between object points within an image and points in the environment are needed. Fiducial marker systems help address this, they are a combination of special printed patterns, some image sensor, and the algorithms to process the images from the image sensor to find the presence, and image location, of these fiducial markers. This distinguishes marker detection from other “marker-less” computer vision. It is not inconvenient in many applications to mount markers on objects or locations, indeed it is sometimes necessary to be able to use imagery from similar or identical objects such as warehouse boxes, or un-textured objects such as blank walls. Reliable and high speed detection of fiducial markers is not a trivial task.
U.S. Pat. No. 7,769,236 B2 (referred to herein as the “Main Detection Algorithm”) describes a marker comprising a polygonal border having at least four non collinear salient points, the interior of this pattern containing a binary digital code. The “Main Detection Algorithm” teaches the steps of detecting an image, using an edge detector to detect an edge in said image, grouping more than one edge into a line segments, and grouping these segments into polygons, and searching the polygon interiors to select the polygons which are images of markers in the scene imaged by a camera. The “Main Detection Algorithm” operates on each image independently with no history of past images. U.S. Pat. No. 7,769,236 B2 is incorporated herein by reference.
FIG. 1 shows the “Main Detection Algorithm” from U.S. Pat. No. 7,769,236 B2. This drawing illustrates processing stages for finding a marker in a single image, with no a priori information.
FIG. 2 shows more details of the “detect polygons using edge-based method” stage of the “Main Detection Algorithm” depicted in FIG. 1. From left to right, top to bottom: Stage A shows the original image, edges are found in the image and joined together to form line segments, which in turn are joined in Stage B to form candidate quadrilaterals, each candidate quadrilateral is then examined in Stage C for an internal valid digital code to produce a final output set of detected markers. This process is repeated for each input image frame. This does not take advantage of the similarity between consecutive image frames in video input.